模拟赛题解/2025.10.8 模拟赛

T1-加法问题（at）

题面

给定 $n$ 个正整数 $a_i$。

乐嘉维林要计算这 $n$ 个数的和，他会先创造一个数 $sum$ 初始是 $0$，然后他会从左往右依次将 $sum$ 加上这个数。

加法是很困难的操作，进位往往是加法中的难点，因此，乐嘉维林希望十进制下进位次数最少（如 $8+167=175$ 会产生一次进位）。

请你将序列 $a_i$ 重排使得乐嘉维林计算过程中进位次数最少，你只需要输出这个次数。

$1\leq n\leq 2\times 10^5,a_i\leq 10^9$。

题解

注意到，只改变顺序而不改变数值的情况下，十进制每一位产生的进位数量是不变的，因此直接模拟进位加和即可。

复杂度 $O(n\log n)$。

T2-树上问题（tp）

题面

给定一个 $n$ 个点的树，点有颜色，问有哪些 $u$ 满足，对于任意的 $v$，路径 $(u,v)$ 上不出现重复颜色。

$1\leq n\leq 2\times10^5,1\leq c_i\leq n$。

题解

我们从一个颜色出现次数不超过 $2$ 入手，此时我们发现限制相当于答案必须在某个子树内/外，直接用 dfs 序列维护即可。

如果 $(u_1,u_2,u_3,u_4,\cdots,u_k)$ 是同一个颜色，我们直接考虑 $(u_1,u_2),(u_1,u_3 ),\cdots,(u_1,u_l)$ 这些二元链产生的限制，那么我们实际上忽略了三元链的情况，然而三元链本身不可能存在解，因此我们只要将满足如上限制得到的答案中的任意一个校验一下即可。

T3-排列计数（cp）

题面

给出三个正整数 $n,m$ 和 $T$。

有多少个 $1\sim n$ 的排列构成的有序 $m$ 元组，$(p_1,p_2,\cdots,p_m)$，满足：

• 字典序：$p_1<p_2<\cdots<p_m$。
• 逆序对数：$p_1>p_2>\cdots>p_m$。

设 $f(n,m)$ 为答案模 $T$ 的值。对于所有 $1\leq i\leq n,1\leq j\leq m$，请你输出 $f(i,j)$。

$1\leq n\leq 14, 1\leq m\leq 30, 2\leq T\leq 10^9+7$。

题解

我们定义 $f(i)$ 为长度为 $i$ 的排列按照字典序排列之后逆序对数量得到的序列。

那么这个题就是要求 $f(n)$ 中长度为 $m$ 的下降子序列。

我们发现 $f(i)$ 是由 $f(i-1)$ 全体加 $0$，加 $1$，$\cdots$，到加 $i-1$ 得到的序列。

那么我们定义 $dp_{i,j,k,l}$ 为 $f(i)$ 中选出长度为 $l$ 开头为 $j$ 结尾为 $k$ 的序列的方案数，那么转移的时候每次 $i$ 变成 $i+1$ 中每一段内部 $dp$ 值除了 $j,k$ 产生了部分平移之外都相同，$dp$ 的合并直接做类似矩阵乘法和卷积的合并即可。

时间复杂度为 $O(n^8m^2)$ 。

T4-剧镇计算（mc）

题面

给定一个整数 $k$，以及一个 $2^k\times2^k$ 的矩阵，每个格子中写有一个数，格子 $(i,j)$ 初始写着 $a_{i,j}$。

给定 $t$ 个二元组 $(x_1,y_1),(x_2,y_2),\cdots,(x_t,y_t)$。

你可以进行如下操作：选择任意 $X,Y$ 满足 $1\leq X,Y\leq 2^k$，任意非负整数 $c$，对于每个 $i$ 从 $1$ 到 $t$，将 $(((X+x_i−1)\bmod2^k)+1, ((Y+y_i−1)\bmod2^k)+1)$ 位置的数替换为 $a((X+xi−1)\bmod2^k)+1,((Y+yi−1)\bmod2^k)+1\oplus c$（这里 $\oplus$ 表示异或操作）。

你的目标是使所有格子中的数都变为 $0$，请输出最小操作次数。

可以证明一定有解。

$1\leq k\leq 9, 0\leq a_i,j < 2 60,1\leq x_i,y_i\leq 2^k,3\leq t\leq min(99, 4^k)$

题解

本题难度极大，选手可以尝试完成一些部分分。

最基础的观察是，如果我们发现一个我们不会对同一个 $(𝑋,𝑌)$ 操作 $2$ 次，因为如果操作了 $c_1$ 和 $c_2$，那么我们不如直接操作 $(𝑋,𝑌,c_1\oplus c_2)$。 接着我们可以发现操作方案本质上是唯一的，所以说我们定义矩阵乘法 $a\times b=M$ 时 $M_{i,j}=\oplus_{x,y} a_{x,y}\times b_{i−x,j−y}$，那么这个问题本质上就是给定两个矩阵 $A,B$，我们要得 到一个矩阵 $C$，满足 $A\times C=B$。

特殊性质A

我们直接尝试求出 $A$ 矩阵的逆矩阵，由于 $A$ 矩阵仅有一行，所以其逆矩阵一定也可以只有一行，直接高斯消元即可。

特殊性质B

我们发现对于矩阵 $T$，$T^2$ 等价于 $T$ 中 $(x,y)$ 点的值转移到位置 $(2x,2y)$（因为其他点位都会被抵消，$((x,y),(𝑧,k))$ 与 $((𝑧,k),(x,y))$ 会转移到同一个位置）。

所以说 $T^{512}$ 实际上就是一个左上角是 $1$ 其他位置是 $0$ 的矩阵。 也就是说 $T^{511}$ 是原矩阵 T 的逆元，所以我们直接计算 $B\times A^{−1}$ 即可。

时间复杂度 $O(k4^k𝑡)$。